COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.turn on "{","}"
C00024 ENDMK
C⊗;
.turn on "{","}";
These are reasonably rough notes which might help you convince people
of the need for sophisticated software-hardware products.
First a discussion of what is needed. Second a discussion of some possible
projects which  are technically realizable and worth pursuing as 
commercial products.

First "Why worry about sophisticated interactive programming?".
Several points need to be made here.

1. There is a significant difference between being able to write
small relatively bug-free programs which run the first time, and
the ability to write large complex systems. The problems of complexity
are not linear. The structure of large language implementations or
operating systems are sufficiently complex⊗↓even with the best 
structuring techniques← that an individual or team simply cannot
be expected to remember all the pertinent details of the implementation.
Current documentation techniques are inadequate. What is more reasonable
is to organize the  information about the %2intentions%* of the system
in such a manner that a reasoning program can use this knowledge
to gauge the correctness of modifications made by the next generation
of systems programmers. At the most trivial level⊗↓clearly within
current technology, but seldom implemented← is an active monitoring of
a type-checking system. A very simple system to assure that modification
maintains the integrity of data types and proper functions calls can
alleviate many possible bugs. A more sophisticated system would use
information supplied by the implementor to check that the expected
behavior was being maintained by the modifications. This additional
information can be given in terms of (1)other procedural information
or (2)non-procedural information. The procedural specifications could
include statements of equivalence of an abstract algorithm to the
algorithm as implemented; typical non-procedural information includes
axiomatizations of parts of the system, perhaps in the form of
input-output assertions. 

The exact form of the intentions is not important. What %2is%* important
is that the original implementor is able to include %2active%* information
which a program understanding system can use to maintain integrity of the
system over possible modifications. To do this kind of deduction requires
several things. First the implementor's final product⊗↓perhaps a
production program, but not necessarily so as we shall see on {yon(P1)}←
and the implementor's intentions must be available in the machine in a 
form which can be manipulated by the ⊗→program understander↔←. That is
both the program and the intentions are present as data structures.
Next a reasonably sophisticated deductive system must be able to
reason using these representations  Proposed modifications to the 
existing program must be checked by the program understander to make sure
that the intentions are not violated⊗↓In the best of such systems
the intentions would be complete enough to guarantee correctness.
All we are asking here is that %2any%* information which the implementor
has can be used.←.

Such reasoning systems are under active consideration for various
domains of expertise. They are large complex programs, but in the face
of the mountains of poorly written, poorly debugged and documented code,
the overhead of such systems are not great.

Such program understanders are closely related to ⊗→programming assistants↔←.
Here the intent is to aid in the programming of the original system.
The user should be able to add information about the program being constructed
and expect that an underlying deductive system or assistant utilize the
information to assure consistency between algorithm and intention.

Such systems are under active investigation at various research establishments:
Stanford, SRI, PARC, MIT, ISI, and Harvard, to name a few. The form
the investigations take varies, but the goal remains constant: help people
write correct programs. 

Indeed these more sophisticated program understanding systems are a second
generation. The first covers the work of Teitleman's DWIM and programmer's 
assistant. These less  ambitious  projects help alleviate some of the
low-level drudgery of debugging very large programs.
The basic idea in DWIM is an attempt to analyze the state of the computation
so as discover the cause of the bug. If the error is "undefined function" or
"unbound variable", the DWIM package will make a valiant attempt to 
discover if the user %2really%* meant to use the offending name or
perhaps the error was caused by a misspelling or typographical error.

At an even lower level, we can make a case for sophisticated display
editors and debuggers as being programming assistants. Anyone who
has used E⊗↓the display editor← or RAID⊗↓the machine-language debugger←
at the Stanford AI Lab soon realizes the
benefits of display facilities.

The display editor, coupled with PUB⊗↓the document compiler←, and the
XGP output device makes an incredibly efficient system for the 
production of complex documents. This trio is most certainly the basis
for a marketable product. The obvious application of such a system to
improve the efficiency of document production is greatly overshadowed
by its  affect on its users. Namely, habitual users develop a 
more  relaxed style of composition. Instead of writing out a document
in long hand; present it to a secretary; revise and correct the copy
and then iterate the process, we tend to compose "on-line"; to think
out-loud if you will. It's a freer kind of expression, leading to a
polished document in a much shorter time span than conventional methods.
Perhaps this editing and composing should be considered a misuse of the
machine. This is the old argument that interactive systems lead to
sloppy programming habits. The answer then was that people tend to check out 
their programs more thoroughly with interactive systems since running
more cases wasn't painfully prohibitive. The argument for the
editing system is similar: people tend to get thing down on
"paper" faster since the cost of revision is very minimal.
I am finishing a 400+ page book using this system. I have typed
all the text myself, even though my typing skill is minimal;
all the diagrams are machine generated, as are the table of contents,
indices, bibliography,  footnotes, and cross-references. The system
has allowed me to produce a book which would not have been feasible
using conventional methods.

What we should be looking for are %2programming%* aids of the caliber
of the %2documentation%* aids exhibited in the E-PUB-XGP cycle.
These programming aids are not just toys for playing clever games on the 
machine. As the complexity of programs goes up and the necessity for
bug-free software becomes more critical, we must supply the professional
programmer with more sophisticated tools. To answer that "Professional
programmers will not be needed if we supply a sufficiently rich
user-interface" is to ignore the problem. Clearly it is the professional
who will have to supply the interface. And if history is any indication,
the %2tools%* which the professional needs to build to supply the more
intricate software will become tamed for the casual user. List-processing
was developed by AI research; the techniques of stacks, garbage collection,
and hashing came out of those investigations. The need for better debugging
tools in AI lead McCarthy and others in the AI community to pursue time-sharing
systems. Counter to many opinions, I believe that the benefits of time-sharing
have little to do with communication between users; rather time-sharing systems
made interactive programming financially feasible in an era when hardware
costs would have prohibited such endeavors. Display-based systems, time-shared
or not, greatly increase the productivity of the user.

Now to specifics. I see a program-understander-assistant as a complex
of programs operating on a data structure representation of a user's
program. By this I mean that for the majority  of the operations which
are performed in developing a program from an idea, it is best to represent
the program as a data structure. When we are editing the program it is a
data structure we are manipulating. We should not think of the program as
a card deck or sting of characters, but rather it is a complex data structure
whose components are determined by the constructs of the programming language.
A program editor should be able  to capitalize on the structuring to
help the user manipulate the representation. The INTERLISP editor, for example,
understands the syntax of LISP and accordingly the command language is oriented
to structure-manipulations of the S-expression representation of the LISP
program.

The initial attempts at running a partially completed program will be
done using an interpreter. Obviously if part of the program is missing
we can't run that, but interpreters can give a lot of information about
the partial execution. Indeed if errors occur, the execution sequence
as stored by the interpreter is an excellent piece of debugging information.
Again INTERLISP excels here; the DWIM package is typically entered
when a bug is detected. Since the program is in the machine in edit-able
form the user can modify it and perhaps continue the computation. If the
computation is completely awry, he might decide to return to a prior
state, modify that, and continue. The UNDO feature of INTERLISP will
do that. None of the described features is particular to LISP; the
techniques can be adapted to other languages; however the fact that
LISP is interpreter oriented and the program is in data structure form
makes the job very much easier.

As our demands for more sophisticated help in the program process
increase the necessity for a structured representation of our program
becomes even more pressing. For example, if we wish to include a subsystem
to transform our program into an equivalent but more efficient program, then
we had better have a structured representation of our program. Such
systems currently exist in dialects of LISP to automatically transform
simple and clear recursive definitions into complex and efficient LISP.
The related task of proving equivalence of algorithms requires a structured
representation. Indeed the most common use of a data structure representation
for a program occurs in the task of compiling code. It is the job
of the parser to transform the input into some tree-like representation.
The basic point here is that for the majority of its life-time, a program
really is best represented as a data structure.

So I envision a helpful programming environment as a cooperating set of
programs, all operating on the structured representation of the user's
program. Some of the subsystems are used explicitly by the user: the editor
evaluator and compiler, for example; some are run in the subsconscious: the
consistency checker, or debugging package.

_______

A related area which should be ripe for large sophisticated systems is the
investigation of large data bases. First, the techniques of abstract data
structures are being re-discovered by the practicioners in this field.
Second, programs written for manipulating such data bases must be 
correct. Indeed, current research at IBM involves verifying the correctness
of the algorithms which manipulate the information in the base.
Third, the systems which access the base must be reasonably intelligent
and high in their human-engineering aspects. I would expect the
manipulation of such large data bases will be one of the first⊗↓and best←
applications of the techniques of AI research and current research in 
program verification and correctness.

.CENT(General Bibliography)

Boyer R., Moore, J  Proving properties of LISP programs. A reasonably sophisticated
LISP system to prove equivalence of LISP programs.

Darlington, J. Papers on Equivalence transformations to LISP programs.

Low, J. PhD thesis at Stanford on picking representations for data structures.

Winograd, T. Breaking the Complexity Barrier again. Some thoughts on the
necessity of helpful programming environments.

%2Papers on the software problem%*

Proceeding of a Symposium on the High Cost of Software, Monterey, Cal 1973

Software Engineering 1968,1969  NATO Conferences.

%2Programming Environments%*

Teitleman, W. PILOT, and its derivatives as programming assistants for LISP.

Swinehart, D. COPILOT; PhD thesis at Stanford on display based controller for
monitoring multiprocessing.

Cheatham, T., Townley, J. A System for Structured Programming

Rich, C. Shrobe, H, Understanding LISP Programs: towards a programmer's apprentice

Wegbreit, B. The ECL Programming System

Infante, R. Proving Programs Correct, Level by Level

Allen, J. NSF proposal for structure oriented display editing in LISP.

%2Papers on languages for better programming%*

Liskov, B. sequence of Computation Structures Group papers dealing with CLU.

Wegbreit, B. Thesis on EL1.

%2Large Data Bases%*

ARPA note on the importance of reliable implementation of very large data bases

Codd, E. Papers on relational data bases.

Sandewall, E. paper on his DABA system

   ...there's many more if you're interested .....